package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/number-of-distinct-averages/'>不同的平均值数目(Number of Distinct Averages)</a>
 * <p>给你一个下标从 0 开始长度为 偶数 的整数数组 nums 。</p>
 * <p>
 * 只要 nums 不是 空数组，你就重复执行以下步骤：
 *     <ul>
 *         <li>找到 nums 中的最小值，并删除它。</li>
 *         <li>找到 nums 中的最大值，并删除它。</li>
 *         <li>计算删除两数的平均值。</li>
 *     </ul>
 *     两数 a 和 b 的 平均值 为 (a + b) / 2 。比方说，2 和 3 的平均值是 (2 + 3) / 2 = 2.5 。
 * </p>
 * <p>返回上述过程能得到的 不同 平均值的数目。</p>
 * <p>注意 ，如果最小值或者最大值有重复元素，可以删除任意一个。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [4,1,4,0,3,5]
 *      输出：2
 *      解释：
 *          1. 删除 0 和 5 ，平均值是 (0 + 5) / 2 = 2.5 ，现在 nums = [4,1,4,3] 。
 *          2. 删除 1 和 4 ，平均值是 (1 + 4) / 2 = 2.5 ，现在 nums = [4,3] 。
 *          3. 删除 3 和 4 ，平均值是 (3 + 4) / 2 = 3.5 。
 *          2.5 ，2.5 和 3.5 之中总共有 2 个不同的数，我们返回 2 。
 *
 * 示例 2：
 *      输入：nums = [1,100]
 *      输出：1
 *      解释：
 *          删除 1 和 100 后只有一个平均值，所以我们返回 1 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>2 <= nums.length <= 100</li>
 *      <li>nums.length 是偶数。</li>
 *      <li>0 <= nums[i] <= 100</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/23 16:29
 */
public class LC2465NumberOfDistinctAverages_S {

    static class Solution {
        public int distinctAverages(int[] nums) {
            int[] cnt = new int[101];
            for (int num : nums) {
                ++cnt[num];
            }
            Set<Double> res = new HashSet<>();
            int left = 0;
            int right = cnt.length - 1;
            while (left <= right) {
                if (cnt[left] == 0) {
                    ++left;
                } else if (cnt[right] == 0) {
                    --right;
                } else {
                    res.add((left + right) / 2.0);
                    --cnt[left];
                    --cnt[right];
                }
            }
            return res.size();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.distinctAverages(new int[]{4, 1, 4, 0, 3, 5}));
        System.out.println(solution.distinctAverages(new int[]{1, 100}));
    }
}
